package com.zsjt.basic.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author zhanb
 * @Auther ZhanBo
 * @Date 2020/5/19
 */
public class InsertSort {

    public static void main(String[] args) {
        int [] arr  ={99,0,1,2,3,7,8};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }


    /**
     * 插入排序
     */
    public static void sort(int [] array){
        //待插入的数字
        int insertVal =0;
        //待插入数字的前一个数字的下标
        int insertIndex=0;

        for (int i =1 ; i< array.length ;i++){
            insertVal= array[i];
            insertIndex = i-1;
            //insertIndex找到插入的位置
            //1、insertIndex >= 0保证下标不越界
            //2、insertVal<array[insertIndex]待插入的数字还没找到插入的位置
            //3、需要将array[insertIndex]后移
            while (insertIndex >= 0 && insertVal<array[insertIndex]){
                array[insertIndex+1] =array[insertIndex];
                insertIndex--;
            }
            if(insertIndex+1 != i ) {
                array[insertIndex+1] = insertVal;
            }
//            System.out.println("第"+i+"轮插入排序");
//            System.out.println(Arrays.toString(array));
        }
    }


    /**
     * 测试插入排序
     * @param n
     */
    public static void test(int n){
        //测试插入排序O(n^2)的速度，给80000个数据
        int  [] arr= new int [n];
        for (int i =0 ;i<arr.length;i++) {
            arr[i] = (int) (Math.random()*n);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println("排序前"+simpleDateFormat.format(date1));
        sort(arr);
        Date date2 = new Date();
        System.out.println("排序后"+simpleDateFormat.format(date2));
    }
}
